1. Field of Invention
The present invention relates generally to methods and apparatus for deoptimizing compiled activations in software applications. More particularly, the present invention relates to methods and apparatus for performing eager deoptimization of compiled activations during the overall execution of a computer program.
2. Description of Relevant Art
Computer systems are often linked across a network, e.g., local area networks, intranets and internets, of computer systems such that they may share resources. Share resources often include software applications. In general, software applications, or computer programs, may be delivered in different formats to different computer systems, due to the fact that each computer system requires software applications to be in a specific format. Alternatively, the computer programs may be delivered to a computer system in a machine-independent form, i.e., as byte codes, in order to enable one form of a computer program to be utilized by many different computer systems.
When computer programs are delivered in a machine-independent form, the programs may be interpreted directly, or the programs may be translated into machine-dependent code, i.e., xe2x80x9cmachine code.xe2x80x9d Programs which are interpreted directly occupy less space in a computer system than programs which are translated into machine code. However, programs which are interpreted directly have slower execution speeds than programs which are translated into machine code, in most cases. As such, the determination of whether or not to interpret a computer program directly, in lieu of translating the computer program into machine code, is often based on the relative importance of space in relation to execution speed.
Some computer systems may be arranged to support both interpreted code and compiled, or machine, code. During the course of executing a program on a system which supports both interpreted and compiled code, it may sometimes be beneficial to eliminate, or delete, a compiled method. Eliminating a compiled method, which contains compiled activations, generally frees space within the computer system. Hence, when additional space is needed on a computer system, a compiled method may be deleted, and replaced with an interpreter code equivalent, because an interpreted method occupies less space than its compiled code equivalent.
In addition, compiled code may have to be discarded because the code was based on assumptions that are no longer valid. By way of example, compiled code may be discarded because a new class was loaded, or because program code was changed. When the assumptions are no longer valid, i.e., no longer hold, if the computer system continues to execute the compiled code, erroneous results may occur. Hence, the computer system must generally cease execution of the compiled code to guard against erroneous results, even in the event that the compiled code is currently executing in one or more activation records.
Each method in a computer program, or application, is typically associated with at least one frame on a computer control stack. As such, when a compiled method is deleted, any frames, i.e., compiled frames, associated with the compiled method must essentially be transformed into interpreter frames. In general, compiled frames may also be transformed into interpreter frames when compiled frames are invalidated, as described above. Transforming such invalid compiled frames into interpreter frames essentially converts invalid frames into valid frames, as will be appreciated by those skilled in the art.
A frame is an activation record that is stored on the control stack, as is well known in the art. The frame pertains to a method, and is arranged to store information for the execution of the method. Information stored in a frame may include control state variables, local variables and an expression stack. A control stack is a stack that is utilized during program execution to store frames for methods, or functions, in their sequential calling order. When a method is called, a frame for the method is pushed onto the control stack. Subsequently, when the method terminates, the frame associated with the method is popped off the stack and the function for the new frame on the top of the control stack resumes execution, i.e., regains control.
A compiled frame may not be transformed into an interpreter code equivalent until the compiled frame is at the top of the control stack, due to the fact that the interpreter code equivalent often requires more space on the control stack than required by the compiled frame. Hence, a method may not be decompiled or deoptimized until the frame which corresponds to the method is at the top of the control stack, since additional space may not be allocated in the middle of the control stack. As such, when the compiled frame is located in the middle of the control stack, e.g., the compiled frame is not the topmost frame in the control stack, the compiled frame may not be replaced by corresponding interpreter frames.
FIG. 1 is a diagrammatic representation of a control stack which includes compiled frames. A control stack 104 includes frames 108 which, as described above, are associated with methods. By way of example, frame 108b is a record which contains activation information associated with a compiled method 116. A stack pointer 112 identifies the location of the topmost frame 108 in stack 104, i.e., frame 108c, which is the frame which is currently executing. Arrow 114 indicates the direction in which stack 104 grows. Therefore, as indicated by arrow 114, frame 108c is the topmost frame in stack 104 and, hence, is the frame with control.
Compiled method 116, and frame 108b, contain information which may be used to create an interpreter code equivalent of compiled method 116. The interpreter code equivalent of compiled method 116 may generally be accessed and, hence, obtained at any time. However, interpreter frames associated with the interpreter code equivalent may occupy a different amount of space on stack 104 than frame 108b. Since frames which contain the interpreter code equivalent of compiled method 116, i.e., interpreter frames, may occupy more space on stack 104 than frame 108b, the interpreter frames may not be inserted into stack 104 until frame 108b is popped to the top of stack 104, as mentioned above. In other words, frame 108b must essentially be the frame with control in stack 104 before method 116 and frame 108b may be deoptimized.
As described above, frame 108b may not be deoptimized when frame 108b is in the middle of stack 104. Accordingly, when it is determined that compiled method 116 is to be deleted, the deletion of compiled method 116 and, hence, the deoptimization of frame 108b must be delayed. Therefore, compiled method 116 may be marked for deletion, and frame 108b may be marked for deoptimization, such that when frame 108b is the topmost frame within stack 104, compiled method 116 is deleted, while frame 108b is deoptimized.
With reference to FIG. 2, the deoptimization of frame 108b in stack 104 of FIG. 1 will be described. When frame 108c, as shown in FIG. 1, is popped from stack 104, then frame 108b is no longer in a middle position within stack 104. In other words, frame 108b becomes the topmost frame in stack 104. Frame 108b may then be replaced by interpreter frame 108bxe2x80x2, which includes an interpreter activation of compiled method 116. Stack pointer 112 may then be set to point to interpreter frame 108bxe2x80x2. Once interpreter frame 108bxe2x80x2 is pushed onto stack 104, compiled method 116 may be deleted, as indicated by deleted compiled method 116xe2x80x2. Space which was previously occupied by compiled method 116 is then available to be reallocated for other uses.
Frame 108b may also be deoptimized just before frame 108b becomes the topmost frame in stack 104. In other words, frame 108b may be deoptimized just as frame 108c is about to return and be popped from stack 104. The deoptimization of frame 108b just before frame 108b becomes the topmost frame is known as xe2x80x9clazyxe2x80x9d deoptimization. Lazy deoptimization is described in xe2x80x9cDebugging Optimized Code with Dynamic Deoptimization,xe2x80x9d by Urs Hxc3x6lzle, Craig Chambers, and David Ungar (ACM SIGPLAN ""92 Conference on Programming Language Design and Implementation, San Francisco, June 1992), which is incorporated herein by reference in its entirety. In lazy deoptimization, deoptimization of a particular compiled frame is delayed until the only frame which is higher in a stack than the particular compiled frame is about to return to the particular compiled frame. As such, in lazy deoptimization, the deoptimization of a frame occurs just as that frame is about to resume execution.
In general, at least some of the computer resources, e.g., memory space, allocated to a compiled method may be slated for reallocation when insufficient resources are available for other purposes. When resources allocated to the compiled method are to be reallocated or redistributed, the compiled method must be deleted, or otherwise deoptimized, in order to free the resources. Therefore, deferring the deletion of the compiled method is often undesirable, since resources which may be used immediately for other purposes will not available until the compiled method is deleted. That is, since the length of delays prior to deletion are often relatively long, depending on factors such as the stack location of a frame that is to be deoptimized, the process of decompiling a compiled method and deoptimizing an associated compiled frame may be inefficient. As such, mechanisms that essentially eliminate the delays associated with decompilation and deoptimization are desired. That is, methods and apparatus which improve the efficiency of dynamic decompilation of compiled methods and dynamic deoptimization of compiled frames associated with a computer program would be desirable.
To achieve the foregoing and other objects of the invention, methods and apparatus for dynamically deoptimizing a frame in a control stack during the execution of a computer program are disclosed. The described methods are particularly suitable for use in computer systems that are arranged to execute both interpreted and compiled byte codes. According to one aspect of the present invention, a computer-implemented method for deoptimizing a compiled method includes creating a data structure. The data structure, which is separate from the control stack, is arranged to store information relating to the compiled method and the frame on that control stack that is to be deoptimized. A reference indicator, such as a pointer, is created to associate the data structure with the frame. The compiled method may then be discarded immediately.
In one embodiment, the data structure is machine-independent, and the decompilation of the compiled method includes deleting the compiled method. In such an embodiment, the new state of the activation of the control stack is an interpreted state. When the data structure is machine-independent, the data structure may be used by a variety of different computers, such that a control stack may be moved from one machine to another machine of the same or different architecture.
According to another aspect of the present invention, a method for dynamically deoptimizing a first frame, which is associated with a compiled method which includes a compiled activation, on a control stack includes decompiling the compiled method. The compiled method may be decompiled when the first frame is located beneath a second frame on the control stack. Decompiling the compiled method includes decompiling the compiled activation to create an interpreter equivalent of the compiled activation. The second frame is eventually popped from the control stack, and an interpreter frame is created from the interpreter equivalent of the compiled activation. The interpreter frame is then pushed onto the stack in place of the first frame. In one embodiment, the interpreter equivalent of the compiled activation is stored in a temporary data structure that is associated with the first frame. In such an embodiment, the data structure may be deleted after the interpreter frame is created.
According to still another aspect of the present invention, a method for dynamically deoptimizing a compiled method associated with a first frame selected from a plurality of frames on a control stack includes creating a data structure that is referenced by the first frame. The data structure, which is separate from the control stack, contains interpreter information relating to the first frame and method information relating to the compiled method. The compiled method is deleted, and the interpreter information is unpacked when the stack pointer associated with the control stack identifies the first frame as the current frame. Unpacking the interpreter information involves the creation of an interpreter frame. The interpreter frame is pushed onto the control stack to replace the first frame.
In one embodiment, the method includes using access information describing the location of local variables and expression state, and placing the interpreter information into the data structure. The interpreter information is accessed using the access information. In such an embodiment, placing the interpreter information into the data structure includes extracting method information from the compiled method, extracting interpreter information from the first frame, and creating at least one interpreted activation using the interpreter information and the method information. In such an embodiment, the interpreter information is migrated into the data structure.